package algorithm;

import java.util.ArrayList;
import java.util.List;

public class leetcode_0093 {
    public List<String> restoreIpAddresses(String s) {
        List<String> list=new ArrayList<>();
        List<String> path=new ArrayList<>();
        int [] num=new int[1];
        if("".equals(s)||s.length()>12) return list;
        dfs(list,path,s,0,num);
        return list;
    }
    public void dfs(List<String> list,List<String> path,String s,int start,int[] num){
        if(start==s.length()){
            if(path.size()<4) return;
            String tem="";
            for(int i=0;i<3;++i){
                tem+=path.get(i);
                tem+=".";
            }
            tem+=path.get(3);
            list.add(tem);
        }
        if(path.size()==4) return;
        for(int i=start+1;i<=s.length();++i){
            if(isnumber(s,start,i-1,num)){
                path.add(num[0]+"");
                dfs(list,path,s,i,num);
                path.remove(path.size()-1);
            }
        }
    }
    public boolean isnumber(String s,int statr,int end,int[] num){
        if(s.charAt(statr)=='0'&&statr!=end) return false;
        int number=0;
        for(int i=statr;i<=end;++i){
            number=number*10+(s.charAt(i)-'0');
        }
        if(number>255) return false;
        num[0]=number;
        return true;
    }
}
